package tree.treerecursion;

import tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Classname : PathSumIII
 * @Description :
 * <a href="https://leetcode.cn/problems/path-sum-iii/">437. 路径总和 III</a>
 * @Author : chentianyu
 * @Date 2023/1/3 22:57
 */


public class PathSumIII {
    // key : 从根节点到当前节点的和；value : 相同和的个数
    // 注意节点累计之后可能超过整型范围，因此使用key使用长整型！
    private Map<Long, Integer> map;

    public int pathSum(TreeNode root, int targetSum) {
        map = new HashMap<>();
        map.put(0L, 1);

        return pathSum(root, targetSum, 0);
    }

    /**
     * 先序遍历实现
     *
     * @param root 当前节点
     * @param targetSum 目标和
     * @param curSum 从根节点到当前节点之和
     * @return
     */
    private int pathSum(TreeNode root, int targetSum, long curSum) {
        if (root == null) return 0;

        curSum += (long) root.val;
        int count = map.getOrDefault(curSum - targetSum, 0);
        map.put(curSum, 1 + map.getOrDefault(curSum, 0));

        count += pathSum(root.left, targetSum, curSum);
        count += pathSum(root.right, targetSum, curSum);

        // 注意当前节点退出后，应把从根节点累加到当前节点的和排除！
        map.put(curSum, map.get(curSum) - 1);
        return count;
    }
}
